import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created by L.jp
 * Description:输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
 * 输入：
 * 9
 *
 * 返回值：
 * [[2,3,4],[4,5]]
 * User: 86189
 * Date: 2022-01-15
 * Time: 20:35
 */
public class Solution {
    /**
     * @param sum: 和为sum的连续正数序列
     * [sum]
     * @return ArrayList<ArrayList < Integer>>  存放最终的结果
     * @description TODO
     */
    public static  ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> ret=new ArrayList<>();
        //采用双指针也就是滑动窗口算法，根据累加和来调整窗口的大小
        //固定窗口起始在1和2之间
        //因为是连续的
        //left和right即指下标也指数值
        int left=1;
        int right=2;
        while(left < right){
            //等差数列求和
            int total=(left + right)*(right - left+1)/2;
            if(total <sum){
                right++;
            }else if(total > sum){
                left++;
            }else{
                //相等的时候找到了一组合适的序列，将他们加入到临时的列表
                ArrayList<Integer> tmp=new ArrayList<>();
                for(int i=left;i<=right;i++){
                    tmp.add(i);
                }
                ret.add(tmp);
                //加入后，继续找下一组合适的值，让坐标的下标++
                left++;
            }
        }
        return  ret;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(FindContinuousSequence(9).toArray()));
    }
}
